import java.util.Random;

//之前是在arr[l,r]的范围中寻找第k小的元素
//修改为arr[l,r)的范围中寻找第k小的元素
public class SelectK {
    public int selectK(int[] arr, int k) {
        return selectK(arr, 0, arr.length, k, new Random());
    }


    public int findKthLargest(int[] nums, int k) {
        int l = 0, r = nums.length;
        Random random = new Random();
        while (l < r) {
            int p = partition(nums, l, r, random);
            if (p==k) return nums[p];
            if (k<p) r = p;
            else l = p + 1;
        }
        return -1;
    }


    /**
     * 在 arr[l,r)的范围中寻找第k小的元素
     *
     * @param arr
     * @param l
     * @param r
     * @param k
     * @param random
     * @return
     */
    private int selectK(int[] arr, int l, int r, int k, Random random) {
        int p = partition(arr, l, r, random);
        if (k == p) return arr[p];
        if (k < p) return selectK(arr, l, p, k, random);
        return selectK(arr, p + 1, r, k, random);
    }


    /**
     * 在arr [l,r)的范围中找到一个随机索引作为基准点 ，小于等于它的元素放到左侧，大于等于它的元素放到右侧
     *
     * @param arr
     * @param l
     * @param r
     * @param random
     * @return
     */
    private int partition(int[] arr, int l, int r, Random random) {
        //在[l,r)的范围内找到一个随机索引
        int p = random.nextInt(r - l) + l;
        swap(arr, p, l);

        //arr[l+1,i-1]<=v ;arr[j+1,r-1]>=v
        int i = l + 1, j = r - 1;
        while (true) {
            while (i <= j && arr[i] < arr[l]) i++;
            while (i <= j && arr[j] > arr[l]) j--;
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 1, 2, 6, 7, 5};
        SelectK selectK = new SelectK();
        int i = selectK.selectK(arr, 0);
        System.out.println(i);
    }

}
